// encode: utf-8 (It is best to open using vscode)
// reference video: https://www.bilibili.com/video/BV1uW4y1G7Gs

#include <iostream>
#include <string>

class Solution
{
public:
    int m_Value[128]{};
    int m_Weight[128]{};
    int m_Dynamic[128][1024]{};

public:
    int knapsack(int n, int c)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= c; j++)
            {
                if (m_Weight[i - 1] > j)
                {
                    m_Dynamic[i][j] = m_Dynamic[i - 1][j];
                }
                else
                {
                    int notPutIn = m_Dynamic[i - 1][j];
                    int putIn = m_Value[i - 1] + m_Dynamic[i - 1][j - m_Weight[i - 1]];
                    m_Dynamic[i][j] = notPutIn > putIn ? notPutIn : putIn;
                }
            }
        }
        return m_Dynamic[n][c];
    }

    void traceback(int n, int c)
    {
        int flag[128]{};
        int len = n;
        while (c > 0 && n > 0)
        {
            if (m_Dynamic[n][c] == m_Dynamic[n - 1][c])
            {
                n = n - 1;
            }
            else
            {
                // std::cout << "Pick No." << n << " item!!" << std::endl;
                flag[n] = 1;
                c = c - m_Weight[n - 1];
                n = n - 1;
            }
        }

        std::cout << "Pick ";
        for (int i = 0; i <= len; i++)
        {
            if (flag[i] == 1)
                std::cout << "NO." << i << " ";
        }
        std::cout << "items!" << std::endl;
    }
};

int main()
{
    Solution slt;
    int n, c, res;
    std::cout << "Please input the numbers and count(n,c):" << std::endl;
    std::cin >> n >> c;
    for (int i = 0; i < n; i++)
    {
        std::cout << "Plesse input the value and weight(" << i + 1 << "/" << n << ")" << std::endl;
        std::cin >> slt.m_Value[i] >> slt.m_Weight[i];
    }
    std::cout << "==================" << std::endl;
    res = slt.knapsack(n, c);
    slt.traceback(n, c);
    std::cout << "The maximum value is " << res << "!" << std::endl;
}